package binarysortTree;

public class Node {
    public static void main(String[] args) {
      Node node  = new Node(8);
        node.add(new Node(10));
//        node.add(new Node(2));
//        node.add(new Node(2));
//        node.add(new Node(2));
//        node.add(new Node(2));
//        node.add(new Node(9));
//        node.add(new Node(7));
//        node.add(new Node(6));
//        node.add(new Node(33));
//        node.add(new Node(111));
//        node.add(new Node(22));
        node.infixSort();
    }
    int val = 0;
    Node left;
    Node right;
    Node(int val){
        this.val = val;
    }
    //添加数据
    public void add(Node node){

        if(this.left==null&&this.val>node.val){
            this.left=node;
            return;
        }
        if(this.right==null&&this.val<=node.val){
            this.right=node;
            return;
        }
        if(node.val<this.val){
            this.left.add(node);
        }
        if(node.val>=this.val){
            this.right.add(node);
        }
    }

    /**
     *
     * @param node
     * @return 1表示左子节点为null  2 表示右子节点为null   0表示左右子节点都有值
     */
    private int isNull(Node node){
        if(node.left==null&&node.right!=null){
            return 2;
        }
        if(node.right==null&&node.left!=null){
            return 1;
        }
        if(node.right==null&&node.left==null){
            return 3;
        }
        return 0;
    }
    private int max(Node node){
          while (node.right!=null){
              node=node.right;
          }
          return  node.val;
    }
    /**
     *
     * @param val  要删除节点的值
     */
    //首先判断删除的是否为父节点.如果是直接删除;并return
    //如果要删除的节点左右都没有值就直接删除
    public void del(int val){
        //找到
        if(this.left!=null&&this.left.val==val){  //如果是左边
            if(isNull(this.left)==3){//如果没有子节点
                this.left=null;
                return;
            }else if(isNull(this.left)==1){//只有一个子节点
                    this.left=this.left.left;
                return;
            }else if(isNull(this.left)==2){//只有一个子节点
                this.left=this.left.right;
                return;
            }else if(isNull(this.left)==0){//两个子节点
                    this.left.val=max(this.left.left);
                    return;
             }
            }else if(this.right!=null&&this.right.val==val){
            if(isNull(this.right)==3){//如果没有子节点
                this.right=null;
                return;
            }else if(isNull(this.right)==1){//只有一个子节点
                this.right=this.right.right;
                return;
            }else if(isNull(this.right)==2){//只有一个子节点
                this.right=this.right.right;
                return;
            }else if(isNull(this.right)==0){//两个子节点
                this.left.val=max(this.right.left);
                return;
            }
        }
            /*
            递归查找值
             */
        if(this.left!=null&&this.left.val>val){
            this.left.del(val);
        }
        if(this.right!=null&&this.right.val<=val){
            this.right.del(val);
        }
    }
    //中序遍历
    public void infixSort(){
        if(this.left!=null){
            this.left.infixSort();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixSort();
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}
